package Sorting;
import java.util.Arrays;

/**
 * @Author：徐志荣
 * @Date：2023/6/30 下午 8:44
 */
public class App {
    //选择排序
    /*
    * 选择排序的思想 :
    * 1. 每一层从待排序的数据元素中选出 最小或最大 的一个元素,存放在序列的起始位置
    * 2. 再从剩余排序元素中继续寻找 最小(大) 元素, 放在已排序序列的末尾
    * 以此类推,直到全部排序的数据元素排完
    * */
    public  static  void selectSortTest(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[minIndex] > arr[j]){
                    minIndex = j;
                }
            }
            if(i != minIndex){
                int tmp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = tmp;
            }
        }
    }
    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }

    private static void quick(int[] arr, int start, int end) {
        if(start >= end){
            return;
        }
        int piovt = partition(arr,start,end);
        quick(arr,start,piovt-1);
        quick(arr,piovt+1,end);

    }

    private static int partition(int[] arr, int left, int right) {
        int tmp = arr[left];
        while(left < right){
            while(left<right){
                if(arr[right] < tmp){
                    arr[left] = arr[right];
                    break;
                }
           right--;
            }
            while(left <right){
                if(arr[left] > tmp){
                    arr[right]  = arr[left];
                    break;
                }
                left++;
            }
        }
        arr[left] = tmp;
        return left;
    }

    public static void main(String[] args) {
        int[] arr = {99,65,49,25,37,9,5,102,152,9996,25,0,45};
//        selectSortTest(arr);
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}
